package leetcode.hot100;

import java.util.*;

public class Solution207 {

    public static void main(String[] args) {

        int numCourses = 2;
        int[][] prerequisites = {{1,0},{0,1}};
        System.out.println(new Solution207().canFinish(numCourses,prerequisites));

    }

    public boolean canFinish1(int numCourses, int[][] prerequisites) {
        //判断有向图里有没有环：拓扑排序
        int[] indegrees = new int[numCourses];
        List<List<Integer>> adjacency = new ArrayList<>();
        Queue<Integer> queue = new LinkedList<>();
        for(int i = 0; i < numCourses; i++)
            adjacency.add(new ArrayList<>());
        // Get the indegree and adjacency of every course.
        for(int[] cp : prerequisites) {
            indegrees[cp[0]]++;
            adjacency.get(cp[1]).add(cp[0]);
        }
        // Get all the courses with the indegree of 0.
        for(int i = 0; i < numCourses; i++)
            if(indegrees[i] == 0) queue.add(i);
        // BFS TopSort.
        while(!queue.isEmpty()) {
            int pre = queue.poll();
            numCourses--;
            for(int cur : adjacency.get(pre))
                if(--indegrees[cur] == 0) queue.add(cur);
        }
        return numCourses == 0;
    }


    public boolean canFinish(int numCourses, int[][] prerequisites) {
        ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            adj.add(new ArrayList<>());
        }
        for (int[] cp: prerequisites) {
            adj.get(cp[0]).add(cp[1]);
        }
        int[] status = new int[numCourses];
        boolean res = true;
        int i = 0;
        while (i<numCourses&&res){
            res = res && dfs(adj,status,i++);
        }
        return res;
    }

    public boolean dfs(ArrayList<ArrayList<Integer>> adj, int[] status, int curNode){
        if(status[curNode]==-1) return true; //已经被其他节点开始的dfs访问过
        if(status[curNode]==1) return false; //已经被本次dfs访问过
        status[curNode] = 1;
        boolean res = true;
        Iterator<Integer> iterator = adj.get(curNode).iterator();
        while (iterator.hasNext()&&res){
            int out = iterator.next();
            res = res && dfs(adj,status,out);
        }
        if(res) status[curNode] = -1;
        return res;
    }
}
